Pada 1961, Borneo dibahagikan kepada empat pentadbiran. Kalimantan, sebuah negeri milik Indonesia yang terletak di selatan Kalimantan. Di utara merupakan Kerajaan Brunei dan dua negeri dibawah pentadbiran British; Sarawak dan Borneo Utara British, yang kemudiannya diberi nama sebagai Sabah. Sebagai bahagian daripada pengunduran daripada pentadbirannya di Asia Tenggara, British cuba menggabungkan pentadbirannya di Kalimantan dengan Semenanjung Tanah Melayu untuk membentuk Malaysia.

Rancangan ini dibantah keras oleh Presiden Indonesia; Presiden Soekarno. Beliau berpendapat bahawa Malaysia ialah sebuah rekaan British, dan penubuhan Malaysia hanya akan memberikan pihak British menguatkan lagi kuasa jajahannya di kepulauan Borneo ini, sehingga memberi ancaman besar terhadap kemerdekaan Indonesia. Filipina juga membuat dakwaan atas Sabah, dengan alasan negeri itu mempunyai hubungan sejarah dengan Filipina melalui Kesultanan Sulu.

Di Brunei, Pemberontak Kalimantan Utara (TNKU) memberontak pada 8 Disember 1962. Mereka melakukan cubaan menculik Sultan Brunei, dan merampas ladang minyak dan menjadikan orang Eropah sebagai tebusan. Sultan Brunei berjaya melepaskan diri dan baginda meminta pertolongan dari British. Baginda mendapat bantuan ketenteraan British, Persekutuan Malaysia dan Gurkha dari Singapura. Pada 16 Disember, Komander Timur Jauh Inggeris (British Far Eastern Commander) menyeru bahawa seluruh pemberontakan utama telah berjaya dipatahkan, dan pada 17 April 1963, pemimpin pemberontak ditangkap dan pemberontakan tersebut berakhir.